package algorithm.easy;

public class Solution53 {

    //输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
    //输出：6
    //解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
    public static int maxSubArray(int[] nums) {
        int[] sum = new int[nums.length];
        int max = nums[0];
        sum[0] = nums[0];
        for(int i=1;i<nums.length;i++){
            sum[i] = Math.max(sum[i-1]+nums[i],nums[i]);
            max = Math.max(sum[i],max);
        }

        return max;
    }

    public static void main(String[] args){
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray(nums));
    }
}
